/**
 * N个怪物，每个怪物有Di的破坏力和Hi的血
 * 你每回合可以造成P的伤害，问杀死所有怪物所承受的最小伤害
 * 对于i和j两个怪物，杀死i要xi个回合，杀死j要xj个回合
 * 则先杀i的条件是：xiDi + (xi + xj)Dj < xjDj + (xi + xj)Di
 * 等价于 xiDj < xjDi
 * 所以可以用这个条件来排序，然后依次处理即可
 */
class Solution {

using llt = long long;
using vll = vector<llt>;
using vi = vector<int>;

public:
    long long minDamage(int power, vector<int>& damage, vector<int>& health) {
        int n = damage.size();
		vi index(n, 0);
		for(int i=0;i<n;++i) index[i] = i;
		sort(index.begin(), index.end(), [&](int a, int b){
            int xa = health[a] / power;
			if(health[a] % power) xa += 1;

			int xb = health[b] / power;
			if(health[b] % power) xb += 1;

			return (llt)xa * damage[b] < (llt)xb * damage[a];
		});

		vll Sum;
		Sum.assign(n, 0LL);
		Sum[n - 1] = damage[index[n - 1]];
		for(int i=n-2;i>=0;--i){
			Sum[i] = Sum[i + 1] + damage[index[i]];
		}

        llt ans = 0;
		for(int i=0;i<n;++i){
			llt d = Sum[i];
			int j = index[i];
			llt x = health[j] / power;
			if(health[j] % power) x += 1;
			ans += x * d;
		}
		return ans;
    }
};